// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

// 求在该柱状图中，能够勾勒出来的矩形的最大面积

#include<bits/stdc++.h>
using namespace std;

// 单调递增栈，看了题解

// 执行用时：
// 148 ms
// , 在所有 C++ 提交中击败了
// 30.63%
// 的用户
// 内存消耗：
// 61.8 MB
// , 在所有 C++ 提交中击败了
// 67.00%
// 的用户

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res =0;
        stack<int> sta;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        sta.push(0);
        for(int i=1;i<heights.size();i++){
            if(heights[i]>=heights[sta.top()]){
                sta.push(i);
            }
            else{
                while (heights[i]<heights[sta.top()]){
                    int mid = sta.top();
                    sta.pop();
                    int left = sta.top();
                    int right = i;
                    int w = right - left -1;
                    int h = heights[mid];
                    res = max(res,w*h);
                }
                sta.push(i);
            }
        }
        return res;
    }
};